#include "list.h"
ListNode *reverseBetween(ListNode *head, int left, int right) {
  if (head == nullptr) {
    return nullptr;
  }

  ListNode *dummy = new ListNode(0, head);  //创建哑结点的主要原因是处理边界情况
  ListNode *pre = dummy;

  ListNode *leftNode = nullptr, *frontLeft, *back = nullptr;
  for (int i = 0; i <= right; ++i) {
    if (i == left - 1) {
      //找到left结点和它前面的那个结点
      frontLeft = pre;
      leftNode = pre->next_;
    } else if (i >= left && i <= right) {
      //局部逆转操作
      pre = leftNode->next_;
      leftNode->next_ = back;
      back = leftNode;
      leftNode = pre;
    } else {
      //不满足条件就更新前驱结点
      pre = pre->next_;
    }
  }

  // frontLeft->next就是逆转后的链表的尾
  // pre最终是right的右边的那个结点
  // back是逆转之后的链表的头
  frontLeft->next_->next_ = pre;
  frontLeft->next_ = back;

  return dummy->next_;
}